In switching networks it frequently happens that a few internal paths are loaded particularly heavily, whereas other internal paths are loaded only lightly. This effect results from uneven traffic loads at the inlets of the switching network, from the traffic characteristic, or from correlations of the incoming traffic. One way of combatting this effect is to first mix the incoming traffic and thus distribute it over the switching network as evenly as possible.
The invention is based on a solution to this problem as is described in an article by D. Bottle and M. A. Henrion, "Alcatel ATM Switch Fabric and Its Properties", Electrical Communication, Vol. 64, No. 2/3, 1990, pages 156 to 165.
That article describes an ATM switching network (ATM=asynchronous transfer mode) consisting of two or more switching stages which, in turn, are constructed from two or more switching elements. The first switching stages represent distribution stages. The switching elements of these stages distribute the incoming cells across all their outputs. In the subsequent stages, path finding takes place. Here, too, multiple paths are possible. For the entire switching network, self-routing multiple-path switching elements are used, which perform a specific type of routing process depending on their stage number. The cells arriving at the input ports of such a switching element can be randomly distributed to a group of multiple links.
How this random distribution of cells to a group of links is effected is not described there.
Another switching network with traffic mixing is described in an article by J. S. Turner, "Design of a Broadcast Packet Network", IEE Infocom Conf., 1986, pp. 667-675.
The switching network consists of a distribution network and a subsequent routing network. The switching elements of the distribution network have two input ports and two output ports. They route an incoming data packet alternately to one output port and the other. If one or both output ports are unavailable, the first port to become available is used.
This method of distributing incoming data packets to two output lines has the disadvantage that the algorithm used is deterministic. This may create new correlations, and the distribution of the data packets is thus not optimal from a traffic point of view.
The problem of distributing data packets to a number of output lines corresponds to the problem of selecting one node from a number of nodes. It has turned out that this problem also arises in many other technical fields, such as in the distribution of processes to a number of available processors in a multiprocessing system. The present solution is also applicable thereto. However, the invention will be described as applied to switching technology.
A mathematician would solve this problem by calculating pseudorandom permutations. However, the algorithms required for this are quite complex and are therefore unsuitable for implementation in hardware, as is necessary for high-speed switching networks, for example.